home *** CD-ROM | disk | FTP | other *** search
/ Experimental BBS Explossion 3 / Experimental BBS Explossion III.iso / c / tde31.zip / FINDREP.C < prev    next >
C/C++ Source or Header  |  1993-08-29  |  51KB  |  1,674 lines
  1. /*******************  start of original comments  ********************/
  2. /*
  3.  * Written by Douglas Thomson (1989/1990)
  4.  *
  5.  * This source code is released into the public domain.
  6.  */
  7.  
  8. /*
  9.  * Name:    dte - Doug's Text Editor program - find/replace module
  10.  * Purpose: This file contains the functions relating to finding text
  11.  *           and replacing text.
  12.  *          It also contains the code for moving the cursor to various
  13.  *           other positions in the file.
  14.  * File:    findrep.c
  15.  * Author:  Douglas Thomson
  16.  * System:  this file is intended to be system-independent
  17.  * Date:    October 1, 1989
  18.  */
  19. /*********************  end of original comments   ********************/
  20.  
  21. /*
  22.  * The search and replace routines have been EXTENSIVELY rewritten.  The
  23.  * "brute force" search algorithm has been replaced by the Boyer-Moore
  24.  * string search algorithm.  This search algorithm really speeds up search
  25.  * and replace operations.
  26.  *
  27.  *                  Sketch of the BM pattern matching algorithm:
  28.  *
  29.  *    while (not found) {
  30.  *       fast skip loop;    <===  does most of the work and should be FAST
  31.  *       slow match loop;   <===  standard "brute force" string compare
  32.  *       if (found) then
  33.  *          break;
  34.  *       shift function;    <===  mismatch, shift and go to fast skip loop
  35.  *    }
  36.  *
  37.  * See:
  38.  *
  39.  *   Robert S. Boyer and J Strother Moore, "A fast string searching
  40.  *     algorithm."  _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
  41.  *
  42.  * See also:
  43.  *
  44.  *   Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
  45.  *    Moore String Matching Algorithm."  _Communications of the ACM_
  46.  *    22 (No. 9): 505-508, 1979.
  47.  *
  48.  *   R. Nigel Horspool, "Practical fast searching in strings." _Software-
  49.  *    Practice and Experience_  10 (No. 3): 501-506, 1980.
  50.  *
  51.  *   Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
  52.  *    String Searching Strategies Revisited."  _SIAM Journal on Computing_
  53.  *    15 (No. 1): 98-105, 1986.
  54.  *
  55.  *   Andrew Hume and Daniel Sunday, "Fast String Searching."  _Software-
  56.  *    Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
  57.  *
  58.  *   Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
  59.  *    _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
  60.  *
  61.  *
  62.  *                            Boyer-Moore in TDE
  63.  *
  64.  * Hume and Sunday demonstrated in their paper that using a simple shift
  65.  * function after a mismatch gives one of the fastest search times with the
  66.  * Boyer-Moore algorithm.  When searching normal text for small patterns
  67.  * (patterns less than 30 characters or so), Hume and Sunday found that the
  68.  * faster the algorithm can get back into the fast skip loop with the
  69.  * largest shift value then the faster the search.  Some algorithms can
  70.  * generate a large shift value, but they can't get back into the skip loop
  71.  * very fast.  Hume and Sunday give a simple method for computing a shift
  72.  * constant that, more often than not, is equal to the length of the search
  73.  * pattern.  They refer to the constant as mini-Sunday delta2 or md2.  From
  74.  * the end of the string, md2 is the first leftmost occurrence of the
  75.  * rightmost character.  Hume and Sunday also found that using a simple string
  76.  * compare as the match function gave better performance than using the C
  77.  * library memcmp( ) function.  The average number of compares in the slow
  78.  * loop was slightly above 1.  Calling the memcmp( ) function to compare 1
  79.  * character slows down the algorithm.  See the Hume and Sunday paper for an
  80.  * excellent discussion on fast string searching.  Incidentally, Hume and
  81.  * Sunday describe an even faster, tuned Boyer-Moore search function.
  82.  *
  83.  * The Boyer-Moore search algorithm in TDE was rearranged so that it is now
  84.  * almost identical to the original version Boyer-Moore described in CACM.
  85.  * The simple shift function in TDE was replaced by the mini-delta2 shift
  86.  * function in the Hume and Sunday paper.
  87.  *
  88.  * I am not very fond of WordStar/TURBO x style search and replace prompting,
  89.  * which is used in the DTE 5.1 editor.  Once the search pattern has been
  90.  * defined, one only needs to press a key to search forwards or backwards.
  91.  * The forward or backward search key may be pressed at any time in any file
  92.  * once the pattern has been entered.  Also, the search case may be toggled
  93.  * at any time in any file once the pattern has been entered.
  94.  *
  95.  * Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a bug when
  96.  * building the ignore skip index array in TDE 1.3 and previous versions.
  97.  * BTW, I added assertions to those functions that build the skip index
  98.  * array to make certain that everything is everything.
  99.  *
  100.  * Thanks also to David Merrill, u09606@uicvm.uic.edu, for recommending a
  101.  * change and the source code for the solution to what can be an annoying
  102.  * feature in the find function.  Pressing <FindForward> before defining
  103.  * the pattern would cause TDE to display an error message.  Since we already
  104.  * know that the search pattern is undefined, we can easily prompt for
  105.  * the search pattern.  I usually tolerate such features until I get tired
  106.  * of being annoyed with error messages and finally write a solution.
  107.  * Dave, thanks for the solution and the easy-to-implement code.  Although
  108.  * such changes are small, they really make for a more comfortable editor.
  109.  *
  110.  * New editor name:  TDE, the Thomson-Davis Editor.
  111.  * Author:           Frank Davis
  112.  * Date:             June 5, 1991, version 1.0
  113.  * Date:             July 29, 1991, version 1.1
  114.  * Date:             October 5, 1991, version 1.2
  115.  * Date:             January 20, 1992, version 1.3
  116.  * Date:             February 17, 1992, version 1.4
  117.  * Date:             April 1, 1992, version 1.5
  118.  * Date:             June 5, 1992, version 2.0
  119.  * Date:             October 31, 1992, version 2.1
  120.  * Date:             April 1, 1993, version 2.2
  121.  * Date:             June 5, 1993, version 3.0
  122.  * Date:             August 29, 1993, version 3.1
  123.  *
  124.  * This modification of Douglas Thomson's code is released into the
  125.  * public domain, Frank Davis.   You may distribute it freely.
  126.  */
  127.  
  128. #include "tdestr.h"
  129. #include "common.h"
  130. #include "tdefunc.h"
  131. #include "define.h"
  132.  
  133.  
  134. /*
  135.  * Name:    get_replacement_flags
  136.  * Purpose: To input find and replace flags.
  137.  * Date:    June 5, 1991
  138.  * Passed:  line:  prompt line
  139.  * Returns: OK if flags were entered, ERROR if user wanted to abort
  140.  */
  141. int  get_replacement_flags( int line )
  142. {
  143. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  144. register int c;
  145. int  func;
  146. int  rc;
  147.  
  148.    save_screen_line( 0, line, line_buff );
  149.    eol_clear( 0, line, g_display.text_color );
  150.    /*
  151.     * options: prompt or no prompt (p/n)?
  152.     */
  153.    s_output( find1, line, 0, g_display.message_color );
  154.    xygoto( strlen( find1 ) + 2, line );
  155.    do {
  156.       c = getkey( );
  157.       func = getfunc( c );
  158.    } while (c != 'P'  &&  c != 'p'  &&  c != 'N'  &&  c != 'n'  &&
  159.             c != RTURN  &&  c != ESC  &&  func != AbortCommand);
  160.    restore_screen_line( 0, line, line_buff );
  161.    switch (c) {
  162.       case 'P' :
  163.       case 'p' :
  164.       case RTURN :
  165.          g_status.replace_flag = PROMPT;
  166.          rc = OK;
  167.          break;
  168.       case 'N' :
  169.       case 'n' :
  170.          g_status.replace_flag = NOPROMPT;
  171.          rc = OK;
  172.          break;
  173.       default :
  174.          rc = ERROR;
  175.    }
  176.    bm.search_defined = rc;
  177.    return( rc );
  178. }
  179.  
  180.  
  181. /*
  182.  * Name:    ask_replace
  183.  * Purpose: Ask user if he wants to (r)place, (s)kip, or (e)xit.
  184.  * Date:    June 5, 1991
  185.  * Returns: TRUE if user wants to replace, ERROR otherwise.
  186.  * Passed:  window:   pointer to current window
  187.  *          finished: TRUE if user pressed ESC or (e)xit.
  188.  */
  189. int  ask_replace( WINDOW *window, int *finished )
  190. {
  191. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  192. register int c;
  193. int  func;
  194. int  prompt_line;
  195. int  rc;
  196.  
  197.    prompt_line = window->cline - 1;
  198.    c = 39 - (strlen( find2 ) >> 1);
  199.    save_screen_line( 0, prompt_line, line_buff );
  200.    /*
  201.     * replace skip exit (r/s/e)?
  202.     */
  203.    s_output( find2, prompt_line, c, g_display.message_color );
  204.    do {
  205.       c = getkey( );
  206.       func = getfunc( c );
  207.    } while (c != 'R' && c != 'r' && c != 'S' && c != 's' && c != 'E' && c != 'e'
  208.           && c != ESC  &&  func != AbortCommand);
  209.    restore_screen_line( 0, prompt_line, line_buff );
  210.    switch (c) {
  211.       case 'R' :
  212.       case 'r' :
  213.          rc = OK;
  214.          break;
  215.       case 'E' :
  216.       case 'e' :
  217.          *finished = TRUE;
  218.       case 'S' :
  219.       case 's' :
  220.          rc = ERROR;
  221.          break;
  222.       default :
  223.          *finished = TRUE;
  224.          rc = ERROR;
  225.          break;
  226.    }
  227.    return( rc );
  228. }
  229.  
  230.  
  231. /*
  232.  * Name:    ask_wrap_replace
  233.  * Purpose: After a wrap, ask user if he wants to (q)uit or (c)ontine.
  234.  * Date:    June 5, 1991
  235.  * Returns: TRUE if user wants to continue, ERROR otherwise.
  236.  * Passed:  window:   pointer to current window
  237.  *          finished: TRUE if user pressed ESC or (q)uit.
  238.  */
  239. int  ask_wrap_replace( WINDOW *window, int *finished )
  240. {
  241. char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
  242. register int c;
  243. int  func;
  244. int  prompt_line;
  245. int  rc;
  246.  
  247.    prompt_line = window->bottom_line;
  248.    save_screen_line( 0, prompt_line, line_buff );
  249.    /*
  250.     * search has wrapped. continue or quit (c/q)?
  251.     */
  252.    set_prompt( find3, prompt_line );
  253.    do {
  254.       c = getkey( );
  255.       func = getfunc( c );
  256.    } while (c != 'Q'  &&  c != 'q'  &&  c != 'C'  &&  c != 'c' &&
  257.           c != ESC  &&  func != AbortCommand);
  258.    restore_screen_line( 0, prompt_line, line_buff );
  259.    switch (c) {
  260.       case 'C' :
  261.       case 'c' :
  262.          rc = OK;
  263.          break;
  264.       case 'Q' :
  265.       case 'q' :
  266.       default :
  267.          *finished = TRUE;
  268.          rc = ERROR;
  269.          break;
  270.    }
  271.    return( rc );
  272. }
  273.  
  274.  
  275. /*
  276.  * Name:    do_replace
  277.  * Purpose: To replace text once match has been found.
  278.  * Date:    June 5, 1991
  279.  * Passed:  window:     pointer to current window
  280.  *          direction:  direction of search
  281.  */
  282. void do_replace( WINDOW *window, int direction )
  283. {
  284. int  old_len;           /* length of original text */
  285. int  new_len;           /* length of replacement text */
  286. int  rcol;
  287. register int net_change;
  288. char *source;           /* source of block move */
  289. char *dest;             /* destination of block move */
  290.  
  291.    old_len = strlen( g_status.pattern );
  292.    new_len = strlen( g_status.subst );
  293.    net_change = new_len - old_len;
  294.    rcol = window->rcol;
  295.  
  296.    /*
  297.     * move the text to either make room for the extra replacement text
  298.     *  or to close up the gap left
  299.     */
  300.  
  301.    g_status.copied = FALSE;
  302.    copy_line( window->ll );
  303.    detab_linebuff( );
  304.  
  305.    if (net_change != 0) {
  306.       assert( rcol + old_len >= 0);
  307.       assert( net_change <= rcol + old_len );
  308.  
  309.       source = g_status.line_buff + rcol + old_len;
  310.       dest  = source + net_change;
  311.  
  312.       assert( g_status.line_buff_len - rcol - old_len >= 0 );
  313.       assert( g_status.line_buff_len - rcol - old_len < MAX_LINE_LENGTH );
  314.  
  315.       memmove( dest, source, g_status.line_buff_len - rcol - old_len );
  316.       g_status.line_buff_len += net_change;
  317.    }
  318.  
  319.    /*
  320.     * insert the replacement text
  321.     */
  322.  
  323.    assert( rcol >= 0 );
  324.    assert( rcol < MAX_LINE_LENGTH );
  325.    assert( g_status.line_buff_len >= 0 );
  326.    assert( g_status.line_buff_len >= rcol );
  327.  
  328.    for (dest=g_status.line_buff+rcol, source=g_status.subst; *source;)
  329.       *dest++ = *source++;
  330.  
  331.    entab_linebuff( );
  332.    window->file_info->modified = TRUE;
  333.    un_copy_line( window->ll, window, TRUE );
  334.    window->ll->dirty = TRUE;
  335.  
  336.    if (direction == FORWARD)
  337.       window->rcol += (new_len - 1);
  338.  
  339.    assert( window->rcol >= 0 );
  340.    show_avail_mem( );
  341. }
  342.  
  343.  
  344. /*
  345.  * Name:    find_string
  346.  * Purpose: To set up and perform a find operation.
  347.  * Date:    June 5, 1991
  348.  * Passed:  window:  pointer to current window
  349.  * Notes:   Keep the search string and boyer-moore stuff until changed.
  350.  */
  351. int  find_string( WINDOW *window )
  352. {
  353. int  direction;
  354. int  new_string;
  355. char pattern[MAX_COLS];  /* text to be found */
  356. long found_line;
  357. long bin_offset;
  358. line_list_ptr ll;
  359. register WINDOW *win;  /* put window pointer in a register */
  360. int  rc;
  361. int  old_rcol;
  362. int  rcol;
  363.  
  364.    switch (g_status.command) {
  365.       case FindForward :
  366.          direction = FORWARD;
  367.          new_string = TRUE;
  368.          break;
  369.       case FindBackward :
  370.          direction = BACKWARD;
  371.          new_string = TRUE;
  372.          break;
  373.       case RepeatFindForward1 :
  374.       case RepeatFindForward2 :
  375.          direction = FORWARD;
  376.          new_string =  bm.search_defined != OK ? TRUE : FALSE;
  377.          break;
  378.       case RepeatFindBackward1 :
  379.       case RepeatFindBackward2 :
  380.          direction = BACKWARD;
  381.          new_string =  bm.search_defined != OK ? TRUE : FALSE;
  382.          break;
  383.       default :
  384.          direction = 0;
  385.          new_string = 0;
  386.          assert( FALSE );
  387.          break;
  388.    }
  389.    win = window;
  390.    entab_linebuff( );
  391.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  392.       return( ERROR );
  393.  
  394.    /*
  395.     * get search text, using previous as default
  396.     */
  397.    if (new_string == TRUE) {
  398.       *pattern = '\0';
  399.       if (bm.search_defined == OK) {
  400.  
  401.          assert( strlen( (char *)bm.pattern ) < MAX_COLS );
  402.  
  403.          strcpy( pattern, (char *)bm.pattern );
  404.       }
  405.  
  406.       /*
  407.        * string to find:
  408.        */
  409.       if (get_name( find4, win->bottom_line, pattern,
  410.                     g_display.message_color ) != OK  ||  *pattern == '\0')
  411.          return( ERROR );
  412.       bm.search_defined = OK;
  413.  
  414.       assert( strlen( pattern ) < MAX_COLS );
  415.  
  416.       strcpy( (char *)bm.pattern, pattern );
  417.       build_boyer_array( );
  418.    }
  419.  
  420.    rc = OK;
  421.    if (bm.search_defined == OK) {
  422.       old_rcol = win->rcol;
  423.       if (mode.inflate_tabs)
  424.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  425.       update_line( win );
  426.       show_search_message( SEARCHING, g_display.diag_color );
  427.       bin_offset = win->bin_offset;
  428.       if (direction == FORWARD) {
  429.          if ((ll = forward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  430.             if (g_status.wrapped && g_status.macro_executing)
  431.                rc = ask_wrap_replace( win, &new_string );
  432.             if (rc == OK)
  433.                find_adjust( win, ll, found_line, rcol );
  434.             else
  435.                win->bin_offset = bin_offset;
  436.          }
  437.       } else {
  438.          if ((ll = backward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  439.             if (g_status.wrapped && g_status.macro_executing)
  440.                rc = ask_wrap_replace( win, &new_string );
  441.             if (rc == OK)
  442.                find_adjust( win, ll, found_line, rcol );
  443.             else
  444.                win->bin_offset = bin_offset;
  445.          }
  446.       }
  447.       if (g_status.wrapped)
  448.          show_search_message( WRAPPED, g_display.diag_color );
  449.       else
  450.          show_search_message( CLR_SEARCH, g_display.mode_color );
  451.       if (ll == NULL) {
  452.          /*
  453.           * string not found
  454.           */
  455.          if (mode.inflate_tabs)
  456.             win->rcol = old_rcol;
  457.          combine_strings( pattern, find5a, (char *)bm.pattern, find5b );
  458.          error( WARNING, win->bottom_line, pattern );
  459.          rc = ERROR;
  460.       }
  461.       show_curl_line( win );
  462.       make_ruler( win );
  463.       show_ruler( win );
  464.    } else {
  465.       /*
  466.        * find pattern not defined
  467.        */
  468.       error( WARNING, win->bottom_line, find6 );
  469.       rc = ERROR;
  470.    }
  471.    return( rc );
  472. }
  473.  
  474.  
  475. /*
  476.  * Name:    build_boyer_array
  477.  * Purpose: To set up the boyer array for forward and backward searches.
  478.  * Date:    June 5, 1991
  479.  * Notes:   Set up one array for forward searches and another for backward
  480.  *          searches.  If user decides to ignore case then fill in array
  481.  *          with reverse case characters so both upper and lower case
  482.  *          characters are defined.
  483.  */
  484. void build_boyer_array( void )
  485. {
  486.  
  487.    /*
  488.     * set up for forward search
  489.     */
  490.    if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep) {
  491.  
  492.       assert( strlen( (char *)sas_bm.pattern ) + 1 < MAX_COLS );
  493.  
  494.       memcpy( bm.pattern, sas_bm.pattern, strlen( (char *)sas_bm.pattern ) +1 );
  495.       bm.search_defined = OK;
  496.    }
  497.  
  498.    if (bm.search_defined == OK) {
  499.       build_forward_skip( &bm );
  500.       bm.forward_md2 = calculate_forward_md2( (char *)bm.pattern,
  501.                                                 bm.pattern_length );
  502.  
  503.       /*
  504.        * set up for backward search
  505.        */
  506.       build_backward_skip( &bm );
  507.       bm.backward_md2 = calculate_backward_md2( (char *)bm.pattern,
  508.                                                   bm.pattern_length );
  509.    }
  510.  
  511.  
  512.    /*
  513.     * build an array for search and seize.
  514.     */
  515.    if (sas_bm.search_defined == OK) {
  516.       build_forward_skip( &sas_bm );
  517.       sas_bm.forward_md2 = calculate_forward_md2( (char *)sas_bm.pattern,
  518.                                                     sas_bm.pattern_length );
  519.  
  520.       /*
  521.        * set up for backward search
  522.        */
  523.       build_backward_skip( &sas_bm );
  524.       sas_bm.backward_md2 = calculate_backward_md2( (char *)sas_bm.pattern,
  525.                                                       sas_bm.pattern_length );
  526.    }
  527. }
  528.  
  529.  
  530. /*
  531.  * Name:    build_forward_skip
  532.  * Purpose: build Boyer-Moore forward skip array
  533.  * Date:    October 31, 1992
  534.  * Passed:  bmp:  pointer to Boyer-Moore structure
  535.  * Notes:   build standard Boyer-Moore forward skip array.
  536.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  537.  *           bug in TDE 1.3 when building the ignore skip index array.
  538.  */
  539. void build_forward_skip( boyer_moore_type *bmp )
  540. {
  541. register unsigned char *p;
  542. register int i;
  543.  
  544.    assert( strlen( (char *)bmp->pattern ) < MAX_COLS );
  545.  
  546.    i = bmp->pattern_length = (int)strlen( (char *)bmp->pattern );
  547.  
  548.    /*
  549.     * set skip index of all characters to length of string
  550.     */
  551.    memset( bmp->skip_forward, i, 256 );
  552.    i--;
  553.  
  554.    /*
  555.     * for each character in string, set the skip index
  556.     */
  557.    for (p=bmp->pattern; i>=0; i--, p++) {
  558.  
  559.       assert( (char)i < bmp->skip_forward[*p] );
  560.  
  561.       bmp->skip_forward[*p] = (char)i;
  562.       if (mode.search_case == IGNORE) {
  563.          if (*p >= 'A' && *p <= 'Z') {
  564.  
  565.             assert( (char)i < bmp->skip_forward[*p+32] );
  566.  
  567.             bmp->skip_forward[*p+32] = (char)i;
  568.          } else if (*p >= 'a' && *p <= 'z') {
  569.  
  570.             assert( (char)i < bmp->skip_forward[*p-32] );
  571.  
  572.             bmp->skip_forward[*p-32] = (char)i;
  573.          }
  574.       }
  575.    }
  576. }
  577.  
  578.  
  579. /*
  580.  * Name:    build_backward_skip
  581.  * Purpose: build Boyer-Moore backward skip array
  582.  * Date:    October 31, 1992
  583.  * Passed:  bmp:  pointer to Boyer-Moore structure
  584.  * Notes:   build standard Boyer-Moore backward skip array.
  585.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  586.  *           bug in TDE 1.3 when building the ignore skip index array.
  587.  */
  588. void build_backward_skip( boyer_moore_type *bmp )
  589. {
  590. register unsigned char *p;
  591. register int i;
  592.  
  593.    i = -bmp->pattern_length;
  594.    memset( bmp->skip_backward, i, 256 );
  595.    i++;
  596.    for (p=bmp->pattern + bmp->pattern_length - 1; i<=0; i++, p--) {
  597.  
  598.       assert( (char)i > bmp->skip_backward[*p] );
  599.  
  600.       bmp->skip_backward[*p] = (char)i;
  601.       if (mode.search_case == IGNORE) {
  602.          if (*p >= 'A' && *p <= 'Z') {
  603.  
  604.             assert( (char)i > bmp->skip_backward[*p+32] );
  605.  
  606.             bmp->skip_backward[*p+32] = (char)i;
  607.          } else if (*p >= 'a' && *p <= 'z') {
  608.  
  609.             assert( (char)i > bmp->skip_backward[*p-32] );
  610.  
  611.             bmp->skip_backward[*p-32] = (char)i;
  612.          }
  613.       }
  614.    }
  615. }
  616.  
  617.  
  618. /*
  619.  * Name:    calculate_forward_md2
  620.  * Purpose: Calculate mini delta2 for forward searches
  621.  * Date:    October 31, 1992
  622.  * Passed:  p:  pointer to pattern
  623.  *          len: length of pattern
  624.  * Notes:   Hume and Sunday (see above) demonstrate in their paper that
  625.  *            using a simple shift function on mismatches with BM
  626.  *            gives one of the fastest run times for general text searching.
  627.  *          mini delta2 is, from the end of the string, the first leftmost
  628.  *            occurrence of the rightmost character.  mini delta2 is 1 in
  629.  *            the worst case.  in previous versions of TDE, the shift function
  630.  *            was hard-coded as 1 -- the worst case.  typically, mini delta2
  631.  *            will be the length of the search pattern.
  632.  */
  633. int  calculate_forward_md2( char *p, int len )
  634. {
  635. int  last_c;
  636. register int i;
  637. register int md2;
  638.  
  639.    md2 = 1;
  640.    i = len - 1;
  641.    last_c = p[i];
  642.    if (mode.search_case == IGNORE) {
  643.       last_c = tolower( last_c );
  644.       for (i--; i >= 0  &&  last_c != tolower( p[i] ); i--)
  645.          ++md2;
  646.    } else
  647.       for (i--; i >= 0  &&  last_c != p[i]; i--)
  648.          ++md2;
  649.  
  650.    assert( md2 >= 1  &&  md2 <= len );
  651.  
  652.    return( md2 );
  653. }
  654.  
  655.  
  656. /*
  657.  * Name:    calculate_backward_md2
  658.  * Purpose: Calculate mini delta2 for backward searches
  659.  * Date:    October 31, 1992
  660.  * Passed:  p:  pointer to pattern
  661.  *          len: length of pattern
  662.  * Notes:   the backward mini delta2 is, from the start of the string, the
  663.  *            first rightmost occurrence of the leftmost character.  in the
  664.  *            worst case, mini delta2 is -1.  typically, mini delta2 is the
  665.  *            negative length of the search pattern.
  666.  */
  667. int  calculate_backward_md2( char *p, int len )
  668. {
  669. int  first_c;
  670. register int i;
  671. register int md2;
  672.  
  673.    md2 = -1;
  674.    i = 1;
  675.    first_c = *p;
  676.    if (mode.search_case == IGNORE) {
  677.       first_c = tolower( first_c );
  678.       for (; i < len  &&  first_c != tolower( p[i] ); i++)
  679.          --md2;
  680.    } else
  681.       for (; i < len  &&  first_c != p[i]; i++)
  682.          --md2;
  683.  
  684.    assert( md2 <= -1  &&  md2 >= -len );
  685.  
  686.    return( md2 );
  687. }
  688.  
  689.  
  690. /*
  691.  * Name:    forward_boyer_moore_search
  692.  * Purpose: search forward for pattern using boyer array
  693.  * Passed:  window:  pointer to current window
  694.  *          rline:   pointer to real line counter
  695.  *          rcol:    pointer to real column variable
  696.  * Returns: position in file if found or NULL if not found
  697.  * Date:    June 5, 1991
  698.  * Notes:   Start searching from cursor position to end of file.  If we hit
  699.  *          end of file without a match, start searching from the beginning
  700.  *          of file to cursor position.  (do wrapped searches)
  701.  */
  702. line_list_ptr forward_boyer_moore_search( WINDOW *window, long *rline,
  703.      int *rcol )
  704. {
  705. register int len;
  706. int  i;
  707. int  end;
  708. register WINDOW *win;  /* put window pointer in a register */
  709. line_list_ptr ll;
  710.  
  711.    /*
  712.     * if cursor is beyond end of line then start at end of line
  713.     */
  714.    win  = window;
  715.    i = win->rcol + 1;
  716.    len = win->ll->len;
  717.    if (i > len)
  718.       i = len;
  719.    if (i < 0)
  720.       i = 0;
  721.  
  722.  
  723.    *rcol = i;
  724.  
  725.    assert( *rcol >= 0 );
  726.  
  727.    *rline = win->rline;
  728.    ll = search_forward( win->ll, rline, (size_t *)rcol );
  729.  
  730.    if (ll == NULL) {
  731.  
  732.       end = 0;
  733.       if (win->ll->next != NULL) {
  734.          end = win->ll->next->len;
  735.          win->ll->next->len = EOF;
  736.       }
  737.  
  738.       /*
  739.        * haven't found pattern yet - now search from beginning of file
  740.        */
  741.       g_status.wrapped = TRUE;
  742.  
  743.       *rcol = 0;
  744.       *rline = 1L;
  745.       ll = search_forward( win->file_info->line_list, rline, (size_t *)rcol );
  746.  
  747.       if (ll == win->ll  &&  *rcol >= win->rcol)
  748.          ll = NULL;
  749.  
  750.       if (win->ll->next != NULL)
  751.          win->ll->next->len = end;
  752.    }
  753.  
  754.    if (ll != NULL)
  755.       bin_offset_adjust( win, *rline );
  756.    return( ll );
  757. }
  758.  
  759.  
  760. /*
  761.  * Name:    search_forward
  762.  * Purpose: search forward for pattern using boyer array
  763.  * Passed:  ll:     pointer to current node in linked list
  764.  *          rline:  pointer to real line counter
  765.  *          offset: offset into ll->line to begin search
  766.  * Returns: position in file if found or NULL if not found
  767.  * Date:    January 8, 1992
  768.  * Notes:   mini delta2 is the first leftmost occurrence of the rightmost
  769.  *            character.
  770.  */
  771. line_list_ptr search_forward( line_list_ptr ll, long *rline, size_t *offset )
  772. {
  773. register int i;
  774. text_ptr p;
  775. text_ptr q;
  776. int  mini_delta2;
  777. unsigned int  mini_guard;
  778. int  guard;
  779. int  pat_len;
  780. int  len_s;
  781. text_ptr s;
  782. char *skip;
  783. boyer_moore_type *bmp;
  784.  
  785.    if (ll->len == EOF)
  786.       return( NULL );
  787.    else {
  788.       if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep)
  789.          bmp = &sas_bm;
  790.       else
  791.          bmp = &bm;
  792.  
  793.       pat_len  = bmp->pattern_length;
  794.       mini_delta2 = bmp->forward_md2;
  795.       skip = bmp->skip_forward;
  796.       p    = bmp->pattern;
  797.  
  798.       i = pat_len - 1;
  799.       guard = -i;
  800.       mini_guard = *p;
  801.       if (mode.search_case != MATCH)
  802.          mini_guard = tolower( mini_guard );
  803.  
  804.       s = ll->line;
  805.       s += *offset;
  806.       len_s = ll->len - *offset;
  807.       for (;;) {
  808.          /*
  809.           * Boyer-Moore fast skip loop.  check character count as we move
  810.           *   down the line.
  811.           */
  812.          for (s+=i, len_s-=i; len_s > 0 && (i = skip[(unsigned char)*s]);
  813.                               s+=i, len_s-=i);
  814.          if (len_s > 0) {
  815.             /*
  816.              * i == 0, possible match.  Boyer-Moore slow match loop.
  817.              */
  818.  
  819.             if (mode.search_case == MATCH) {
  820.                if (s[guard] != mini_guard)
  821.                   goto shift_func;
  822.  
  823.                q = s + 1 - pat_len;
  824.                for (i=0; i < pat_len; i++)
  825.                   if (q[i] != p[i])
  826.                      goto shift_func;
  827.             } else {
  828.                if ((unsigned int)tolower( s[guard] ) != mini_guard)
  829.                   goto shift_func;
  830.  
  831.                q = s + 1 - pat_len;
  832.                for (i=0; i < pat_len; i++)
  833.                   if (tolower( q[i] ) != tolower( p[i] ))
  834.                      goto shift_func;
  835.             }
  836.             *offset = (size_t)(q - ll->line);
  837.  
  838.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  839.  
  840.             return( ll );
  841.          }
  842. shift_func:
  843.          if (len_s <= 0) {
  844.             ++*rline;
  845.             ll = ll->next;
  846.             s = ll->line;
  847.             if (ll->len == EOF)
  848.                return( NULL );
  849.             len_s = ll->len;
  850.             i = pat_len - 1;
  851.          } else
  852.             i = mini_delta2;
  853.       }
  854.    }
  855. }
  856.  
  857.  
  858. /*
  859.  * Name:    backward_boyer_moore_search
  860.  * Purpose: search backward for pattern using boyer array
  861.  * Passed:  window:  pointer to current window
  862.  *          rline:   pointer current real line counter
  863.  *          rcol:    pointer to real column
  864.  * Returns: position in file if found or NULL if not found
  865.  * Date:    June 5, 1991
  866.  * Notes:   Start searching from cursor position to beginning of file. If we
  867.  *          hit beginning end of file without a match, start searching from the
  868.  *          end of file to cursor position.  (do wrapped searches)
  869.  */
  870. line_list_ptr backward_boyer_moore_search( WINDOW *window, long *rline, int *rcol )
  871. {
  872. int  i;
  873. int  len;
  874. int  end;
  875. register WINDOW *win;  /* put window pointer in a register */
  876. line_list_ptr ll;
  877.  
  878.    win  = window;
  879.    *rline = win->rline;
  880.  
  881.    /*
  882.     * see if cursor is on EOF line.  if so, move search start to previous node.
  883.     */
  884.    if (win->ll->len != EOF) {
  885.       ll = win->ll;
  886.       i  = win->rcol - 1;
  887.       i += bm.pattern_length - 1;
  888.       len = ll->len;
  889.       if (i >= len)
  890.          i = len - 1;
  891.    } else {
  892.       ll = win->ll->prev;
  893.       --*rline;
  894.       i = 0;
  895.       if (ll != NULL)
  896.          i = ll->len - 1;
  897.    }
  898.    *rcol = i;
  899.    ll = search_backward( ll, rline, (size_t *)rcol );
  900.  
  901.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  902.  
  903.       end = 0;
  904.       if (win->ll->prev != NULL) {
  905.          end = win->ll->prev->len;
  906.          win->ll->prev->len = EOF;
  907.       }
  908.  
  909.       /*
  910.        * haven't found pattern yet - now search from end of file
  911.        */
  912.       g_status.wrapped = TRUE;
  913.       ll = win->file_info->line_list_end;
  914.       if (ll->prev != NULL)
  915.          *rcol = ll->prev->len;
  916.       else
  917.         *rcol = 0;
  918.       *rline = win->file_info->length;
  919.       ll = search_backward( ll->prev, rline, (size_t *)rcol );
  920.  
  921.       if (ll == win->ll  &&  *rcol <= win->rcol)
  922.          ll = NULL;
  923.  
  924.       if (win->ll->prev != NULL)
  925.          win->ll->prev->len = end;
  926.    }
  927.    if (ll != NULL)
  928.       bin_offset_adjust( win, *rline );
  929.    return( ll );
  930. }
  931.  
  932.  
  933. /*
  934.  * Name:    search_backward
  935.  * Purpose: search backward for pattern using boyer array
  936.  * Passed:  ll:  pointer to node in linked list to start search
  937.  *          rline:  pointer to real line counter
  938.  *          offset:  offset into ll->line to start search
  939.  * Returns: position in file if found else return NULL
  940.  * Date:    January 8, 1992
  941.  * Notes:   Start searching from cursor position to beginning of file.
  942.  *          mini delta2 is the first rightmost occurrence of the leftmost character.
  943.  */
  944. line_list_ptr search_backward( line_list_ptr ll, long *rline, size_t *offset )
  945. {
  946. register int i;
  947. text_ptr p;
  948. int  mini_delta2;
  949. int  pat_len;
  950. int  len_s;
  951. text_ptr s;
  952.  
  953.    if (ll == NULL)
  954.       return( NULL );
  955.    if (ll->len == EOF)
  956.       return( NULL );
  957.    else {
  958.       mini_delta2 = bm.backward_md2;
  959.       pat_len  = bm.pattern_length;
  960.       p = bm.pattern;
  961.  
  962.       i = -bm.pattern_length + 1;
  963.  
  964.       s = ll->line;
  965.       s += *offset;
  966.       len_s = *offset + 1;
  967.       for (;;) {
  968.  
  969.          /*
  970.           * Boyer-Moore fast skip loop.  check character count as we move
  971.           *   up the line.
  972.           */
  973.          for (s+=i, len_s+=i; len_s > 0 &&
  974.                  (i = bm.skip_backward[(unsigned char)*s]); s+=i, len_s+=i);
  975.          if (len_s > 0) {
  976.             /*
  977.              * i == 0, possible match.  Boyer-Moore slow match loop.
  978.              */
  979.             if (mode.search_case == MATCH) {
  980.                for (i=0; i < pat_len; i++)
  981.                   if (s[i] != p[i])
  982.                     goto shift_func;
  983.             } else {
  984.                for (i=0; i < pat_len; i++)
  985.                   if (tolower( s[i] ) != tolower( p[i] ))
  986.                      goto shift_func;
  987.             }
  988.             *offset =(size_t)(s - ll->line);
  989.  
  990.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  991.  
  992.             return( ll );
  993.          }
  994. shift_func:
  995.          if (len_s <= 0) {
  996.             --*rline;
  997.             ll = ll->prev;
  998.             if (ll == NULL)
  999.                return( NULL );
  1000.             if (ll->len == EOF)
  1001.                return( NULL );
  1002.             len_s = ll->len;
  1003.             s = ll->line + len_s - 1;
  1004.             i = 1 - pat_len;
  1005.          } else
  1006.             i = mini_delta2;
  1007.       }
  1008.    }
  1009. }
  1010.  
  1011.  
  1012. /*
  1013.  * Name:    show_search_message
  1014.  * Purpose: display search status
  1015.  * Date:    January 8, 1992
  1016.  * Passed:  i:     index into message array
  1017.  *          color: color to display message
  1018.  */
  1019. void show_search_message( int i, int color )
  1020. {
  1021.    /*
  1022.     *  0 = blank
  1023.     *  1 = wrapped...
  1024.     *  2 = searching
  1025.     *  3 = replacing
  1026.     *  4 = nfa choked
  1027.     */
  1028.    assert( i >= 0  &&  i <= 4);
  1029.    s_output( find7[i], g_display.mode_line, 67, color );
  1030. }
  1031.  
  1032.  
  1033. /*
  1034.  * Name:    bin_offset_adjust
  1035.  * Purpose: place cursor on screen given a position in file - default cline
  1036.  * Date:    June 5, 1991
  1037.  * Passed:  window:  pointer to current window
  1038.  *          rline:   real line position some where in the file
  1039.  * Notes:   in binary mode, we keep an accurate count of the offset of the
  1040.  *          cursor from the beginning of the file.
  1041.  */
  1042. void bin_offset_adjust( WINDOW *window, long rline )
  1043. {
  1044. line_list_ptr   node;
  1045. long            found_distance;
  1046.  
  1047.    assert( rline >= 1L  &&  rline <= window->file_info->length );
  1048.  
  1049.    found_distance = window->rline - rline;
  1050.    node = window->ll;
  1051.    if (found_distance < 0) {
  1052.       while (found_distance++ < 0) {
  1053.          window->bin_offset += node->len;
  1054.          node = node->next;
  1055.       }
  1056.    } else if (found_distance > 0) {
  1057.       while (found_distance-- > 0) {
  1058.          node = node->prev;
  1059.          window->bin_offset -= node->len;
  1060.       }
  1061.    }
  1062.    assert( window->bin_offset >= 0 );
  1063. }
  1064.  
  1065.  
  1066. /*
  1067.  * Name:    find_adjust
  1068.  * Purpose: place cursor on screen given a position in file - default cline
  1069.  * Date:    June 5, 1991
  1070.  * Passed:  window:  pointer to current window
  1071.  *          ll:   position anywhere in file
  1072.  *          rline:  real line number of ll in the file
  1073.  *          rcol:   real column of ll in the file
  1074.  * Notes:   ll could be anywhere in file.  Find the start of line that
  1075.  *          ll is on.  Determine if start of line is behind or ahead of
  1076.  *          current line.  Once that is done, it is easy to determine if ll
  1077.  *          is on screen.  Lastly, current cursor position becomes start of
  1078.  *          ll line - reposition and display.
  1079.  */
  1080. void find_adjust( WINDOW *window, line_list_ptr ll, long rline, int rcol )
  1081. {
  1082. int  cmd;
  1083. long test_line;
  1084. file_infos *file;
  1085. register WINDOW *win;  /* put window pointer in a register */
  1086.  
  1087.    win = window;
  1088.    file = win->file_info;
  1089.  
  1090.    /*
  1091.     * given a real column, adjust for inflated tabs.
  1092.     */
  1093.    if (mode.inflate_tabs)
  1094.       rcol = detab_adjust_rcol( ll->line, rcol );
  1095.  
  1096.    /*
  1097.     * if p, start of found line, is greater than current line, see if
  1098.     * p is between current line and bottom line on screen.
  1099.     */
  1100.    if (win->rline < rline) {
  1101.       /*
  1102.        * test_line is the number of lines between rline and found line.
  1103.        */
  1104.       test_line = rline - win->rline;
  1105.       if ((long)win->cline + test_line <= (long)win->bottom_line)
  1106.          win->cline += (int)test_line;
  1107.       else
  1108.          file->dirty = LOCAL;
  1109.  
  1110.    /*
  1111.     * if p, start of found line, is less than current line, see if
  1112.     * p is between current line and top line on screen.
  1113.     */
  1114.    } else if (win->rline > rline) {
  1115.       test_line = win->rline - rline;
  1116.       if ((long)win->cline - test_line > (long)(win->top_line+win->ruler-1))
  1117.          win->cline -= (int)test_line;
  1118.       else
  1119.          file->dirty = LOCAL;
  1120.       if (rline < (long)(win->cline - (win->top_line+win->ruler-1)))
  1121.          win->cline = (int)rline + win->top_line+win->ruler - 1;
  1122.    }
  1123.  
  1124.    /*
  1125.     * cursor line becomes found line.  check if column is on screen.
  1126.     */
  1127.    win->rline = rline;
  1128.    win->ll    = ll;
  1129.    if (file->dirty == LOCAL && (win->cline == win->bottom_line ||
  1130.                                 win->cline == win->top_line + win->ruler)) {
  1131.       cmd = g_status.command;
  1132.       if (cmd == RepeatFindForward1    ||  cmd == RepeatFindBackward1 ||
  1133.           cmd == DefineDiff            ||  cmd == RepeatDiff          ||
  1134.           cmd == FindRegX              ||  cmd == RepeatFindRegX      ||
  1135.           cmd == DefineGrep            ||  cmd == RepeatGrep) {
  1136.          center_window( win );
  1137.       } else if (cmd == ReplaceString) {
  1138.          if (win->visible)
  1139.             center_window( win );
  1140.       }
  1141.    }
  1142.    check_virtual_col( win, rcol, rcol );
  1143. }
  1144.  
  1145.  
  1146. /*
  1147.  * Name:    replace_string
  1148.  * Purpose: To set up and perform a replace operation.
  1149.  * Date:    June 5, 1991
  1150.  * Passed:  window:  pointer to current window
  1151.  */
  1152. int  replace_string( WINDOW *window )
  1153. {
  1154. int  direction;
  1155. char pattern[MAX_COLS];  /* the old and replacement text */
  1156. int  net_change;
  1157. int  sub_len;
  1158. int  file_changed;
  1159. int  finished;
  1160. int  use_prev_find;
  1161. int  rc;
  1162. int  rcol;
  1163. int  rcol_limit;
  1164. int  wrapped;
  1165. int  wrapped_state;
  1166. long found_line;
  1167. long line_limit;
  1168. line_list_ptr   ll;
  1169. WINDOW          wp;
  1170. WINDOW          old_wp;
  1171. register        WINDOW *win;    /* put window pointer in a register */
  1172. int             visible;
  1173.  
  1174.    win = window;
  1175.    direction = get_replace_direction( win );
  1176.    if (direction == ERROR)
  1177.       return( ERROR );
  1178.  
  1179.    entab_linebuff( );
  1180.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  1181.       return( ERROR );
  1182.  
  1183.    /*
  1184.     * get the search pattern, using the previous as the default
  1185.     */
  1186.    *pattern = '\0';
  1187.    if (g_status.replace_defined == OK) {
  1188.  
  1189.       assert( strlen( g_status.pattern ) < MAX_COLS );
  1190.  
  1191.       strcpy( pattern, g_status.pattern );
  1192.    }
  1193.  
  1194.    /*
  1195.     * string to find
  1196.     */
  1197.    if (get_name( find9, win->bottom_line, pattern,
  1198.                  g_display.message_color ) != OK  ||  *pattern == '\0')
  1199.       return( ERROR );
  1200.  
  1201.    assert( strlen( pattern ) < MAX_COLS );
  1202.  
  1203.    strcpy( g_status.pattern, pattern );
  1204.  
  1205.    /*
  1206.     * get the replacement text, using the previous as the default
  1207.     */
  1208.    *pattern = '\0';
  1209.    if (g_status.replace_defined == OK) {
  1210.  
  1211.       assert( strlen( g_status.subst ) < MAX_COLS );
  1212.  
  1213.       strcpy( pattern, g_status.subst );
  1214.    }
  1215.    if (get_name( find10, win->bottom_line, pattern,
  1216.                  g_display.message_color ) != OK)
  1217.       return( ERROR );
  1218.  
  1219.    assert( strlen( pattern ) < MAX_COLS );
  1220.  
  1221.    strcpy( g_status.subst, pattern );
  1222.    sub_len = strlen( pattern );
  1223.    strcpy( (char *)bm.pattern, g_status.pattern );
  1224.    net_change = sub_len - strlen( g_status.pattern );
  1225.  
  1226.    /*
  1227.     * get the replace flags, Prompt or NoPrompt
  1228.     */
  1229.    if (get_replacement_flags( win->bottom_line ) != OK)
  1230.       return( ERROR );
  1231.  
  1232.    build_boyer_array( );
  1233.    dup_window_info( &wp, win );
  1234.    update_line( win );
  1235.    g_status.replace_defined = OK;
  1236.  
  1237.    if (mode.inflate_tabs)
  1238.       win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol );
  1239.  
  1240.    rc = OK;
  1241.    visible = win->visible;
  1242.    if (g_status.replace_flag == NOPROMPT) {
  1243.       wp.visible = FALSE;
  1244.       xygoto( win->ccol, win->cline );
  1245.       show_search_message( REPLACING, g_display.diag_color );
  1246.    }
  1247.    wrapped_state = wrapped = FALSE;
  1248.    finished = FALSE;
  1249.    file_changed = FALSE;
  1250.    use_prev_find = FALSE;
  1251.    line_limit = 0;
  1252.    rcol_limit = 0;
  1253.    dup_window_info( &old_wp, &wp );
  1254.    if (direction == FORWARD) {
  1255.       if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1256.                 !g_status.control_break) {
  1257.          line_limit = found_line;
  1258.          rcol_limit = rcol;
  1259.          if (g_status.wrapped)
  1260.             wrapped_state = wrapped = TRUE;
  1261.          rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1262.                                    &file_changed, direction );
  1263.          if (rc == ERROR &&  g_status.replace_flag == PROMPT  && wrapped_state)
  1264.             use_prev_find = TRUE;
  1265.       } else {
  1266.          /*
  1267.           * string not found
  1268.           */
  1269.          error( WARNING, win->bottom_line, find8 );
  1270.          finished = TRUE;
  1271.          rc = ERROR;
  1272.       }
  1273.       while (finished == FALSE) {
  1274.          use_prev_find = wrapped_state = FALSE;
  1275.          dup_window_info( &old_wp, &wp );
  1276.          if (wp.visible == TRUE)
  1277.             update_line( &wp );
  1278.          if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1279.              !g_status.control_break) {
  1280.             if (g_status.wrapped)
  1281.                wrapped_state = wrapped = TRUE;
  1282.             if (wrapped) {
  1283.                if (found_line > line_limit) {
  1284.                   finished = TRUE;
  1285.                   use_prev_find = TRUE;
  1286.                } else if (found_line == line_limit  &&  rcol == rcol_limit) {
  1287.                   finished = TRUE;
  1288.                   use_prev_find = TRUE;
  1289.                }
  1290.             }
  1291.             if (finished == FALSE) {
  1292.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1293.                                          &file_changed, direction );
  1294.                if (rc == OK && ll == win->ll && rcol < rcol_limit)
  1295.                   rcol_limit += net_change;
  1296.                if (rc == ERROR &&  g_status.replace_flag == PROMPT  &&
  1297.                                         wrapped_state)
  1298.                   use_prev_find = TRUE;
  1299.             }
  1300.          } else {
  1301.             if (g_status.control_break)
  1302.                rc = getkey( );
  1303.             /*
  1304.              * string not found     or   control break
  1305.              */
  1306.             if (g_status.control_break)
  1307.                error( WARNING, win->bottom_line, cb );
  1308.             else if (wp.visible)
  1309.                error( WARNING, win->bottom_line, find8 );
  1310.             finished = TRUE;
  1311.             rc = ERROR;
  1312.          }
  1313.       }
  1314.    } else {
  1315.       if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1316.           !g_status.control_break) {
  1317.          line_limit = found_line;
  1318.          rcol_limit = rcol;
  1319.          if (g_status.wrapped)
  1320.             wrapped_state = wrapped = TRUE;
  1321.          replace_and_display( &wp, ll, found_line, rcol, &finished, &file_changed,
  1322.                               direction );
  1323.          if (rc == ERROR &&  g_status.replace_flag == PROMPT  && wrapped_state)
  1324.             use_prev_find = TRUE;
  1325.       } else {
  1326.          /*
  1327.           * string not found
  1328.           */
  1329.          error( WARNING, win->bottom_line, find8 );
  1330.          finished = TRUE;
  1331.          rc = ERROR;
  1332.       }
  1333.       while (finished == FALSE) {
  1334.          use_prev_find = wrapped_state = FALSE;
  1335.          dup_window_info( &old_wp, &wp );
  1336.          if (wp.visible == TRUE)
  1337.             update_line( &wp );
  1338.          if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1339.              !g_status.control_break) {
  1340.             if (g_status.wrapped)
  1341.                wrapped_state = wrapped = TRUE;
  1342.             if (wrapped) {
  1343.                if (found_line < line_limit) {
  1344.                   finished = TRUE;
  1345.                   use_prev_find = TRUE;
  1346.                } else if (found_line == line_limit  &&  rcol == rcol_limit) {
  1347.                   finished = TRUE;
  1348.                   use_prev_find = TRUE;
  1349.                }
  1350.             }
  1351.             if (finished == FALSE) {
  1352.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1353.                                          &file_changed, direction );
  1354.                if (rc == OK && found_line == line_limit && rcol < rcol_limit)
  1355.                   rcol_limit += net_change;
  1356.                if (rc == ERROR  && g_status.replace_flag == PROMPT  &&
  1357.                                         wrapped_state)
  1358.                   use_prev_find = TRUE;
  1359.             }
  1360.          } else {
  1361.             if (g_status.control_break)
  1362.                rc = getkey( );
  1363.             /*
  1364.              * string not found    or   control break
  1365.              */
  1366.             if (g_status.control_break)
  1367.                error( WARNING, win->bottom_line, cb );
  1368.             else if (wp.visible)
  1369.                error( WARNING, win->bottom_line, find8 );
  1370.             finished = TRUE;
  1371.             rc = ERROR;
  1372.          }
  1373.       }
  1374.    }
  1375.  
  1376.    if (g_status.replace_flag == PROMPT) {
  1377.       if (use_prev_find)
  1378.          dup_window_info( &wp, &old_wp );
  1379.       dup_window_info( win, &wp );
  1380.    } else {
  1381.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1382.       g_status.wrapped = FALSE;
  1383.    }
  1384.  
  1385.    if (mode.inflate_tabs)
  1386.       win->rcol = detab_adjust_rcol( win->ll->line, win->rcol );
  1387.  
  1388.    win->visible = visible;
  1389.    check_virtual_col( win, win->rcol, win->ccol );
  1390.    if (win->file_info->dirty != LOCAL && win->file_info->dirty != GLOBAL)
  1391.       show_curl_line( win );
  1392.    if (file_changed)
  1393.       win->file_info->modified = TRUE;
  1394.    make_ruler( win );
  1395.    show_ruler( win );
  1396.    show_ruler_pointer( win );
  1397.    return( rc );
  1398. }
  1399.  
  1400.  
  1401. /*
  1402.  * Name:    replace_and_display
  1403.  * Purpose: To make room for replacement string
  1404.  * Date:    June 5, 1991
  1405.  * Passed:  window:            pointer to current window
  1406.  *          ll:                pointer to position of pattern in file
  1407.  *          rline:             pointer to real line counter
  1408.  *          rcol:              pointer to real column
  1409.  *          finished:          stop replacing on this occurrence?
  1410.  *          modified:          skip this replacement?
  1411.  *          direction:         direction of search
  1412.  * Notes:   Show user where pattern_location is on screen if needed.
  1413.  *          Replace and display if needed.   Always ask the user if he
  1414.  *          wants to do wrapped replacing.
  1415.  */
  1416. int  replace_and_display( WINDOW *window, line_list_ptr ll, long rline,
  1417.                      int rcol, int *finished, int *modified, int direction )
  1418. {
  1419. register int rc;
  1420. file_infos *file;
  1421. register WINDOW *win;  /* put window pointer in a register */
  1422.  
  1423.    win = window;
  1424.    file = win->file_info;
  1425.    rc = OK;
  1426.    if (g_status.wrapped) {
  1427.       rc = ask_wrap_replace( win, finished );
  1428.       g_status.wrapped = FALSE;
  1429.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1430.    }
  1431.    if (rc == OK) {
  1432.       find_adjust( win, ll, rline, rcol );
  1433.       if (win->visible == TRUE) {
  1434.          make_ruler( win );
  1435.          show_ruler( win );
  1436.          show_ruler_pointer( win );
  1437.          xygoto( win->ccol, win->cline );
  1438.          if (file->dirty) {
  1439.             display_current_window( win );
  1440.             file->dirty = FALSE;
  1441.          } else
  1442.             show_curl_line( win );
  1443.       }
  1444.  
  1445.       if (g_status.replace_flag == PROMPT && rc == OK) {
  1446.          show_line_col( win );
  1447.          rc = ask_replace( win, finished );
  1448.       }
  1449.       if (rc == OK) {
  1450.          do_replace( win, direction );
  1451.          *modified = TRUE;
  1452.          file->dirty = GLOBAL;
  1453.          if (win->visible == TRUE) {
  1454.             show_changed_line( win );
  1455.             file->dirty = FALSE;
  1456.          }
  1457.       }
  1458.       if (mode.inflate_tabs) {
  1459.          if (win->rcol >= 0)
  1460.             win->rcol = entab_adjust_rcol( ll->line, ll->len, win->rcol );
  1461.       }
  1462.    }
  1463.    return( rc );
  1464. }
  1465.  
  1466.  
  1467. /*
  1468.  * Name:    scan_forward
  1469.  * Purpose: To find the corresponding occurrence of target, ignoring
  1470.  *           embedded pairs of opp and target, searching forwards.
  1471.  * Date:    June 5, 1991
  1472.  * Passed:  rline:  pointer to real line position
  1473.  *          rcol:   pointer to real column position
  1474.  *          ll:     pointer to current node in linked list
  1475.  *          opp:    the opposite to target
  1476.  *          target: the string to be found
  1477.  *          rc:     OK if found, ERROR otherwise
  1478.  * Returns: the location of the corresponding target in the text buffer
  1479.  * Notes:   Every 8,000 characters, check pointer forward.
  1480.  */
  1481. line_list_ptr scan_forward( long *rline, int *rcol, line_list_ptr ll,
  1482.                             char opp, char target, int *rc )
  1483. {
  1484. text_ptr s;
  1485. int  count = 0;          /* number of unmatched opposites found */
  1486. int  len;
  1487. register char c;
  1488.  
  1489.    *rc = OK;
  1490.    if (ll != NULL  &&  ll->len != EOF) {
  1491.       len = ll->len - *rcol - 1;
  1492.       s = ll->line + *rcol + 1;
  1493.       while (ll->len != EOF) {
  1494.          while (len > 0) {
  1495.  
  1496.             assert( s != NULL);
  1497.  
  1498.             c = *s++;
  1499.             --len;
  1500.             if (opp == c)
  1501.                count++;
  1502.             else if (target == c) {
  1503.                if (count == 0)
  1504.                  goto match;
  1505.                --count;
  1506.             }
  1507.          }
  1508.          ++*rline;
  1509.          ll  = ll->next;
  1510.          s   = ll->line;
  1511.          len = ll->len;
  1512.       }
  1513. match:
  1514.       if (ll->len != EOF) {
  1515.  
  1516.          assert( s != NULL );
  1517.  
  1518.          *rcol = (int)(s - ll->line - 1);
  1519.       } else
  1520.          *rc = ERROR;
  1521.    } else
  1522.       *rc = ERROR;
  1523.  
  1524.    if (*rc == OK) {
  1525.       assert( *rcol >= 0 );
  1526.       assert( *rcol < ll->len );
  1527.    }
  1528.  
  1529.    return( ll );
  1530. }
  1531.  
  1532.  
  1533. /*
  1534.  * Name:    scan_backward
  1535.  * Purpose: To find the corresponding occurrence of target, ignoring
  1536.  *           embedded pairs of opp and target, searching backwards.
  1537.  * Date:    June 5, 1991
  1538.  * Passed:  rline:  pointer to real line position
  1539.  *          rcol:   pointer to real column position
  1540.  *          ll:     pointer to current node in linked list
  1541.  *          opp:    the opposite to target
  1542.  *          target: the string to be found
  1543.  *          rc:     OK if found, ERROR otherwise
  1544.  * Returns: the location of the corresponding target in the text buffer
  1545.  */
  1546. line_list_ptr scan_backward( long *rline, int *rcol, line_list_ptr ll,
  1547.                              char opp, char target, int *rc )
  1548. {
  1549. text_ptr s;
  1550. int  count = 0;         /* number of unmatched opposites found */
  1551. register int len;
  1552. register char c;
  1553.  
  1554.    *rc = OK;
  1555.    if (ll != NULL  &&  ll->len != EOF) {
  1556.       s = ll->line + *rcol - 1;
  1557.       len = *rcol;
  1558.       while (ll != NULL) {
  1559.          while (len > 0) {
  1560.  
  1561.             assert( s != NULL );
  1562.  
  1563.             c = *s--;
  1564.             if (opp == c)
  1565.                count++;
  1566.             else if (target == c) {
  1567.                if (count == 0)
  1568.                  goto match;
  1569.                --count;
  1570.             }
  1571.             --len;
  1572.          }
  1573.          --*rline;
  1574.          ll = ll->prev;
  1575.          if (ll != NULL) {
  1576.             len = ll->len;
  1577.             s = ll->line + len - 1;
  1578.          }
  1579.       }
  1580. match:
  1581.       if (ll != NULL) {
  1582.  
  1583.          assert( s != NULL );
  1584.  
  1585.          *rcol = (int)(s - ll->line + 1);
  1586.       } else
  1587.          *rc = ERROR;
  1588.    } else
  1589.       *rc = ERROR;
  1590.  
  1591.    if (*rc == OK) {
  1592.       assert( *rcol >= 0 );
  1593.       assert( *rcol < ll->len );
  1594.    }
  1595.  
  1596.    return( ll );
  1597. }
  1598.  
  1599.  
  1600. /*
  1601.  * Name:    match_pair
  1602.  * Purpose: To find the corresponding pair to the character under the
  1603.  *           cursor.
  1604.  * Date:    June 5, 1991
  1605.  * Passed:  window:  pointer to current window
  1606.  * Notes:   Searching is very simple-minded, and does not cope with things
  1607.  *          like brackets embedded within quoted strings.
  1608.  */
  1609. int  match_pair( WINDOW *window )
  1610. {
  1611. long rline;
  1612. char c;
  1613. register WINDOW *win;  /* put window pointer in a register */
  1614. int  rc;
  1615. int  rcol;
  1616. line_list_ptr ll;
  1617.  
  1618.    win = window;
  1619.    entab_linebuff( );
  1620.    rline = win->rline;
  1621.    ll = win->ll;
  1622.    if (un_copy_line( ll, win, TRUE ) == ERROR)
  1623.       return( ERROR );
  1624.    /*
  1625.     * make sure the character under the cursor is one that has a
  1626.     *  matched pair
  1627.     */
  1628.    if (ll->len == EOF || win->rcol >= ll->len)
  1629.       return( ERROR );
  1630.    rcol = win->rcol;
  1631.    c = *(ll->line + rcol);
  1632.    rc = OK;
  1633.  
  1634.    /*
  1635.     * find the matching pair
  1636.     */
  1637.    switch (c) {
  1638.       case '[':
  1639.          ll = scan_forward( &rline, &rcol, ll, '[', ']', &rc );
  1640.          break;
  1641.       case '(':
  1642.          ll = scan_forward( &rline, &rcol, ll, '(', ')', &rc );
  1643.          break;
  1644.       case '{':
  1645.          ll = scan_forward( &rline, &rcol, ll, '{', '}', &rc );
  1646.          break;
  1647.       case ']':
  1648.          ll = scan_backward( &rline, &rcol, ll, ']', '[', &rc );
  1649.          break;
  1650.       case ')':
  1651.          ll = scan_backward( &rline, &rcol, ll, ')', '(', &rc );
  1652.          break;
  1653.       case '}':
  1654.          ll = scan_backward( &rline, &rcol, ll, '}', '{', &rc );
  1655.          break;
  1656.       default :
  1657.          rc = ERROR;
  1658.    }
  1659.  
  1660.    /*
  1661.     * now show the user what we have found
  1662.     */
  1663.    if (rc == OK) {
  1664.       update_line( win );
  1665.       bin_offset_adjust( win, rline );
  1666.       find_adjust( win, ll, rline, rcol );
  1667.       if (!win->file_info->dirty)
  1668.          show_curl_line( win );
  1669.       make_ruler( win );
  1670.       show_ruler( win );
  1671.    }
  1672.    return( rc );
  1673. }
  1674.